1. Field of the Invention
The present invention generally relates to vector graphics processing, and more particularly to anti-aliasing of a vector graphics image.
2. Discussion of the Background
In recent years, computer graphics have been employed for representing digital images, for example, as raster graphics, vector graphics, and the like. A raster graphics image can be stored and manipulated as a grid of pixels. Typically, the grid of pixels can be rectangular, having a horizontal dimension, and a vertical dimension. The raster graphics image can be displayed, for example, on a display device, such as a monitor, on media, such as paper, and the like. The color of each pixel can be individually defined. Typically, each pixel can be represented by independent values for the red, green, and blue components of the pixel. In addition, a value for a transparency component or “alpha” value can be included for each pixel of the graphics image. Accordingly, a raster graphics image can be determined by its resolution (e.g., the total number of pixels), and by its color depth (e.g., the amount of information in each pixel).
By contrast, a vector graphics image can include geometric objects, such as curves, lines, polygons, and the like. With a vector graphics image, rather than storing and manipulating each pixel of an image, information describing the geometric objects included in the image can be stored. For example, in the case of a geometric object, such as a circle, the stored information for drawing the circle can include the radius of the circle, the location of the center point of the circle, the style and color of the stroke line used for the circle, the style and color of the fill used for the circle, and the like.
Often, a geometric object can be decomposed into more simple geometric objects. For example, a quadrangle can be decomposed into two triangles. In the vector graphics arts, the term “primitive” can be used to refer to a basic or primitive element of a geometric object in a vector graphics image, and can include points, lines, planes, circles, spheres, triangles, polygons, and the like. When a primitive includes one or more line segments, these line segments can be referred to as “edges” in the vector graphics arts. For example, a quadrangle is a polygon consisting of four edges.
The advantages of vector graphics over raster graphics can include significantly smaller file size due to the minimal amount of information needed to be stored. In addition, the file size does not depend on the dimensions of the geometric object or objects included in the image. Furthermore, vector graphics can be used for describing both two-dimensional and three-dimensional geometric objects, and a vector graphics image can be scaled without losing its quality.
Even though a vector graphics image can be stored and modified in the above-described format, including the drawing information, the vector graphics image typically can be converted to a raster graphics image for display, and referred to as “rasterization.” Typically, rasterization can include looping through each of the primitives, determining which pixels in the image a current primitive affects, and modifying the corresponding pixels accordingly.
While rasterizing a vector graphics image, “anti-aliasing” often can be employed to smooth the resulting raster graphics image, and can include manipulating the apparent smoothness of contours in the graphics image, for example, by manipulating the transparency of pixels neighboring such contours. Anti-aliasing commonly is employed in the art of computer graphics, particularly in the context of conventional computers, such as desktop computers, servers, and the like. For example, scalable fonts displayed on a computer screen can be anti-aliased, including determining for each pixel used to display a character, how much of that pixel is occupied by the character, and drawing that pixel with the corresponding degree of opacity. For example, when drawing a black character on a white background, if a pixel should ideally be half filled (e.g., such as by diagonal line from corner to corner), the pixel might be drawn with a 50% gray level.
In addition, various implementations of anti-aliasing for three-dimensional graphics have been developed. For example, a typical anti-aliasing solution for polygon-based three-dimensional rendering can include full-screen anti-aliasing in which a whole frame buffer is first rendered in a higher resolution and then sampled down. By using a suitable sampling scheme, the anti-aliasing can be achieved with a relatively low amount of samples and without sacrificing performance. However, this approach is not particularly suitable for two-dimensional rendering, because the requirements for anti-aliasing quality in two-dimensional rendering are higher. In other words, anti-aliasing in two-dimensional rendering would require a significantly larger amount of samples, resulting in a considerable penalty with regards to memory usage. Furthermore, such approach requires a special arrangement of samples in the output bitmap in order to achieve a suitable sampling pattern. Accordingly, two-dimensional anti-aliasing algorithms are typically used with bitmaps having a regular grid of samples for sample arrangement. Therefore, an anti-aliasing scheme used in connection with two-dimensional rendering should be able to operate with bitmaps having a regular grid of samples for sample arrangement.
Typically, texture data has already been filtered such that a higher sampling frequency need only be employed at polygon edges. Accordingly, some anti-aliasing techniques employ such an observation for calculating anti-aliasing only for polygon data, for example, by means of coverage masks where blending of color values fetched from different polygons is required only if the coverage masks define a partial fill area.
Schemes for two-dimensional polygon anti-aliasing algorithms can be classified into sample-based approaches, and analytical approaches. Sample-based approaches typically employ high-resolution data internally and calculate pixel intensities from such data. Generation of the high-resolution data can include rasterizing directly to a high-resolution buffer or using table lookup for edge masks that are used for composing the high-resolution buffer. Simply rendering at a higher resolution and then downscaling can be considered a simplified version of the sample-based approach. However, such sample-based approaches are relatively expensive with respect to bandwidth and memory usage, since a large amount of samples has to be processed.
Analytical approaches, on the other hand, attempt to calculate exact pixel coverage of a polygon by means of mathematical analysis. Analytical approaches can produce a higher amount of tones at polygon edges than sample-based approaches. Furthermore, analytical approaches do not suffer from sampling artifacts. However, analytical approaches are computationally expensive, for example, due to requiring clipping at pixel level and between polygons. In addition, even though sampling artifacts are avoided, there can be artifacts of other types, if optimizations are used in connection with analytical approaches. Furthermore, analytical approaches are not easily extendable for supporting various fill rules, and rather a polygon typically can be subdivided into smaller polygons or triangles, resulting in a time consuming step in the processing.
The above described anti-aliasing methods and algorithms typically are employed with high processing power computers, wherein powerful processors typically are required to implement such anti-aliasing techniques. With modern computers that are often equipped with a separate graphics processing unit in addition to a central processing unit, such techniques do not present a significant problem. However, with the rising popularity of various handheld devices, such as mobile telephones, personal digital assistants, handheld computers, and the like, which include a display for displaying graphics, but typically have processing power significantly lower than that of conventional computers, there is a need for an anti-aliasing scheme which provides a varied range of features and which is nevertheless efficient (e.g., not requiring a high-end platform), and simple to implement.
In addition, certain graphics standards have been developed, such the OpenVG 1.0 standard by Khronos group of Jul. 28, 2005, incorporated by reference herein, which provides an application programming interface (API) for hardware accelerated two-dimensional vector and raster graphics, including anti-aliasing. Accordingly, the OpenVG specification provides a set of device independent specifications to be implemented (e.g., by device manufacturers) in order to provide hardware acceleration on devices ranging from wristwatches to full microprocessor-based desktop and server machines. However, the OpenVG specification does not teach or suggest how to actually implement their specifications.